package someTestExcemple.huaweiOd.binarySearch;
//华为OD机试 - 组装最大可靠性设备 - 二分查找（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/146127670
//用最少钱组装可靠性最高的设备
//1.通用是二分搜索，左边界可靠性最低的元器件，右边界可靠性最高的元器件
import java.util.*;
public class MountingEquipment {
    static class Component {
        int type;
        int stability; //可靠性
        int price; //价格
        public Component(int type,int stability,int price) {
            this.type = type;
            this.stability = stability;
            this.price =  price;
        }
    }
    private static int maxStability = -1; //默认不能组装出类任何设备就输出-1
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt(); //总预算
        int m = sc.nextInt(); //需要元器件类型
        int n = sc.nextInt(); //总元器件数量
        List<Component> list = new ArrayList<>();
        for(int i=0;i<n;i++) {
            int type = sc.nextInt();
            int stability = sc.nextInt();
            int price = sc.nextInt();
            Component component = new Component(type,stability,price);
            list.add(component);
        }
        //这里排序失效是因为 stream().sorted() 方法不会改变原始的 List，而是返回一个新的排序后的流。
        //你没把这个排序后的流赋值出去
//        list.stream().sorted(new Comparator<Component>() {
//            @Override
//            public int compare(Component o1, Component o2) {
//                return o1.stability - o2.stability;
//            }
//        });
        list.sort((o1, o2) -> o1.stability - o2.stability);
        //找出稳定值的左右边界
        int left = list.get(0).stability;
        int right = list.get(list.size()-1).stability;
        //list再按价格进行升序
        list.sort((o1,o2)->o1.price-o2.price);
        System.out.println(binarySearch(list,left,right,m,S));

    }
    public static int binarySearch(List<Component> list,int left,int right,int typeNum,int budget) {
        while(left <=right) {
            int mid = left + (right-left)/2;
            if(canMatch(list,mid,typeNum,budget)) {
                maxStability = Math.max(maxStability,mid);
                left = mid+1;
            } else {
                right = mid -1;
            }
        }
        return maxStability;
    }
    public static boolean canMatch(List<Component> list,int target,int typeNum,int budget) {
        Set<Integer> typeSet = new HashSet<>();
        int usedMoney =0;
        boolean result = false;
        for(Component component : list) {
            //选可靠性不小于目标值的，且没被选过的种类元器件
            //由于list最后是按价格升序，所以同一品类的一定是先get到了价格最低的
            if(component.stability >= target && !typeSet.contains(component.type)) {
                typeSet.add(component.type);
                usedMoney+= component.price;
                if(usedMoney > budget) {
                    result = false;
                    break;
                }
                if(typeSet.size() >= typeNum) {
                    result = true;
                    break;
                }
            }
        }
        return result;
    }

}
